/*
 * @lc app=leetcode.cn id=429 lang=typescript
 *
 * [429] N 叉树的层序遍历
 */

// @lc code=start
/**
 * Definition for node.
 * class Node {
 *     val: number
 *     children: Node[]
 *     constructor(val?: number) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.children = []
 *     }
 * }
 */

interface Cell {
  node: Node;
  deep: number;
}

function levelOrder(root: Node | null): number[][] {
  const ans: number[][] = [];
  if (root === null) return ans;
  // 初始化
  const queue: Cell[] = [{ node: root, deep: 0 }];
  // BFS
  while (queue.length) {
    const curr = queue.shift()!;
    if (curr.deep === ans.length) {
      ans.push([]);
    }
    ans[curr.deep].push(curr.node.val);
    for (const child of curr.node.children) {
      queue.push({ node: child, deep: curr.deep + 1 });
    }
  }
  return ans;
}
// @lc code=end
